"""
sort 排序算法训练
"""
import time

l = [4, 3, 3, 1, 2, 5, 8, 4, 7, 6, 9]


class Sort:
	def __init__(self, list_):
		self.list_ = list_

	def __str__(self):
		return f"{self.list_}"

	# 冒泡sort
	def bubble(self, osc=False):
		"""
		冒泡排序(小到大 升序 和 大到小 降序)
		:param osc: 默认为升false, true为降序
		"""
		list_ = self.list_
		if not osc:  # 升序
			for i in range(len(list_) - 1):  # 表示列表总长度
				for j in range(i + 1, len(list_)):  # 表示下一个元素
					if list_[i] > list_[j]:  # 如果当前元素比下一个元素大,则位置两两交换,即升序排法(小于则降序排法)
						list_[i], list_[j] = list_[j], list_[i]  # 两两交换
		else:  # 降序
			for i in range(len(list_) - 1):
				for j in range(i + 1, len(list_)):  # range(len(list_) - 1 -i) 跟 range(i + 1, len(list_)) 效果是一样的
					if list_[i] < list_[j]:
						list_[i], list_[j] = list_[j], list_[i]

	# 选择排序
	def select(self, is_not=False):
		"""
		选择排序(默认升序排法), 假设一个列表中第一个元素是最小值,与列表后面元素挨个进行比对,如果比第一个元素小,则这两个元素交换,
			在与后面的元素继续比对,直到比对完一轮. 以此循环比对,直到整个列表交换完成
		:param is_not: False(默认升序排法), True为降序排法
		:return: 无
		"""
		if is_not:
			for i in range(len(self.list_) - 1):  # 每轮选出一个最小值,需要 len(self.list_) - 1 轮
				current = i  # 假设 self.list_[i] 是最小值
				for j in range(i + 1, len(self.list_)):
					if self.list_[current] > self.list_[j]:
						current = j  # 如果当前元素比后一个元素大,则将后一个元素覆盖当前元素

				if current != i:  # 当比对完一轮时, 进行交换,将最小值换到current位置上,进行下一轮比对,直到结束
					self.list_[i], self.list_[current] = self.list_[current], self.list_[i]
		else:  # 降序排法
			for i in range(len(self.list_) - 1):  # 每轮选出一个最小值,需要 len(self.list_) - 1 轮
				current = i  # 假设 self.list_[i] 是最小值
				for j in range(i + 1, len(self.list_)):
					if self.list_[current] < self.list_[j]:
						current = j  # 如果当前元素比后一个元素大,则将后一个元素覆盖当前元素

				if current != i:  # 当比对完一轮时, 进行交换,将最小值换到current位置上,进行下一轮比对,直到结束
					self.list_[i], self.list_[current] = self.list_[current], self.list_[i]

	# 插入排序
	def insertion(self):
		"""
		插入排序(升序), 从第一个元素开始, 都与上一个元素开始比较, 如果比前一个元素小, 则交换,直到完成
		"""
		for i in range(1, len(self.list_)):         # 列表第二个元素
			mix_ = i
			j = i - 1                               # 前一个元素
			while j >= 0 and self.list_[j] > mix_:
				self.list_[i] = self.list_[j]       # 第一位向前移动一位 self.list_[i] 等于 self.list_[j + 1]
				j -= 1                              # 向前一位,不能越界
			self.list_[j + 1] = mix_                # 将第二位的元素,插入到第一位元素的位置

	# 快速排序
	def quick(self, low, high):
		"""
		快速排序. sub_sort()是quick()方法重构提取出去的方法,是为一体的
		:param low:列表的第一位 位置
		:param high: 列表的最后一位 位置
		:return: 无, 直接操作列表
		"""
		if low < high:  # low 表示列表第一个下标, high表示最后一个下标, 即low<high就是终止条件
			key = self.sub_sort(low, high)
			self.quick(low, key - 1)  # key-1 作为新的上限
			self.quick(key + 1, high)  # key+1 作为新的下限 以此形成递归操作

	# 快速排序 --> 完成一轮交换, 前后移位,交换处理
	def sub_sort(self, low, high):
		"""
		快速排序 --> 完成一轮交换, 前后移位,交换处理
		:param low: 列表的第一个下标
		:param high: 列表的最后一个下标
		:return: 返回当前的基准数,作为下一次循环的基准
		"""
		# 选定基准
		x = self.list_[low]
		# low向后, high向前比对移位
		while low < high:
			# 第一段,后面的数往前移
			while self.list_[high] >= x and high > low:
				high -= 1
			self.list_[low] = self.list_[high]
			# 第二段,前面的数往后移
			while self.list_[low] < x and low < high:
				low += 1
			self.list_[high] = self.list_[low]

		# 插入基准数
		self.list_[low] = x
		return low  # 返回基准数,作为下一次循环的基准

	# 二分查找
	def search(self, key):
		"""
		二分查找
		:param key: 查找列表那个元素
		:return: 返回查找元素的下标
		"""
		low, high = 0, len(self.list_) - 1  # 列表第一个和最后一个索引
		while high < high:
			mid = (low + high) // 2
			if self.list_[mid] < key:
				low = mid + 1
			elif self.list_[mid] > key:
				high = mid - 1
			else:
				return mid



if __name__ == '__main__':
	si = time.time()
	so = Sort(l)
	# so.quick(0, len(l)-1)  # 快速排序
	# so.select()
	# so.insertion()
	print(so.search(1))
	print(l)
	print(time.time() - si)
